package cut_stock;

import gurobi.GRB;
import gurobi.GRBEnv;
import gurobi.GRBException;
import gurobi.GRBLinExpr;
import gurobi.GRBModel;
import gurobi.GRBVar;

import java.util.Arrays;
import Jama.Matrix;

public class CutStock {

    public static void solver(int stockLength, double[] specs, double[] requirements) {
        System.out.println(stockLength);
        System.out.println(Arrays.toString(specs));
        System.out.println(Arrays.toString(requirements));

        int n = specs.length;

        // 生成b
        Matrix b = new Matrix(n, 1, 0);
        for (int i = 0; i < n; i++) {
            b.set(i, 0, requirements[i]);
        }
        Matrix b_new = b.copy();

        // 构造初始B_inverse
        Matrix B_inverse = new Matrix(n, n);
        for (int i = 0; i < n; i++) {
            B_inverse.set(i, i, (int) (stockLength / specs[i]));
        }
        B_inverse = B_inverse.inverse();

        long startTime = System.currentTimeMillis();
        while (true) {

            // 构造IP模型，算出进基变量的系数
            Matrix p = CutStockUtils.getXin(B_inverse, stockLength, specs);

            // 更新p和b
            p = B_inverse.times(p);
            b_new = B_inverse.times(b);

            // 判断是否达到最优解
            if (p.norm1() == 0) {
                break;
            }

            // 获得出基变量在B_inverse中的索引
            int index = CutStockUtils.getXout(B_inverse, b_new, p);

            // 更新B_inverse
            B_inverse = CutStockUtils.updateB_inverse(B_inverse, p, index);
        }

        // 输出最优方案（不取整）
        System.out.println("specs: " + Arrays.toString(specs));
        Matrix B = B_inverse.inverse();
        for (int i = 0; i < n; i++) {
            System.out.println("方案" + (i + 1) + ": " + b_new.get(i, 0) + "根");
            B.getMatrix(0, n - 1, i, i).transpose().print(n, 2);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
    }

    public static void main(String[] args) {
        DataReader reader = new DataReader();
        reader.loadFile("src/column_generation/cutstock.dat");
        solver(reader.stockLength, reader.specs, reader.requirements);
    }
}

class CutStockUtils {
    static Matrix getXin(Matrix B_inverse, int stockLength, double[] specs) {
        int n = B_inverse.getColumnDimension();
        Matrix Cbv = new Matrix(1, n, 1);
        Matrix p = new Matrix(n, 1, 0);
        try {

            // Create empty environment, set options, and start
            GRBEnv env = new GRBEnv(true);
            env.start();

            // Create empty model
            GRBModel model = new GRBModel(env);

            // Create variables
            GRBVar[] x = model.addVars(n, GRB.INTEGER);

            // Set objective
            GRBLinExpr expr = new GRBLinExpr();
            expr.addTerms(Cbv.times(B_inverse).getArray()[0], x);
            expr.addConstant(-1);
            model.setObjective(expr, GRB.MAXIMIZE);

            // Add constraint
            expr = new GRBLinExpr();
            expr.addTerms(specs, x);
            model.addConstr(expr, GRB.LESS_EQUAL, stockLength, "c0");

            // Optimize model
            model.optimize();

            if (model.get(GRB.DoubleAttr.ObjVal) > 0) {
                for (int i = 0; i < n; i++) {
                    p.set(i, 0, x[i].get(GRB.DoubleAttr.X));
                }
            }

            // Dispose of model and environment
            model.dispose();
            env.dispose();

        } catch (GRBException e) {
            System.out.println("Error code: " + e.getErrorCode() + ". " + e.getMessage());
        }
        return p;
    }

    static int getXout(Matrix B_inverse, Matrix b, Matrix p) {
        int n = B_inverse.getColumnDimension();
        // 计算出基变量
        double theta = Double.MAX_VALUE;
        int index = -1;
        for (int i = 0; i < n; i++) {
            double temp = b.get(i, 0) / p.get(i, 0);
            System.out.println(temp);
            if (temp < 0) {
                continue;
            }
            if (temp < theta) {
                theta = temp;
                index = i;
            }
        }
        return index;
    }

    static Matrix updateB_inverse(Matrix B_inverse, Matrix p, int index) {
        int n = B_inverse.getColumnDimension();
        Matrix E = new Matrix(n, n);
        // 构造E
        for (int i = 0; i < n; i++) {
            Matrix temp = new Matrix(n, 1);
            if (i == index) {
                for (int j = 0; j < n; j++) {
                    if (j == index) {
                        temp.set(j, 0, 1 / p.get(j, 0));
                    } else {
                        temp.set(j, 0, -p.get(j, 0) / p.get(index, 0));
                    }
                }
            } else {
                for (int j = 0; j < n; j++) {
                    if (j == i) {
                        temp.set(j, 0, 1);
                    } else {
                        temp.set(j, 0, 0);
                    }
                }
            }
            E.setMatrix(0, n - 1, i, i, temp);
        }
        return E.times(B_inverse);
    }
}
